home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d12 / cc03.arc / QSORT.C < prev   
Encoding:
C/C++ Source or Header  |  1986-03-15  |  4.1 KB  |  156 lines
  1. /*                                  QSORT.C
  2.  *                                  =======
  3.  *   Quit sort routine from Dr. Dobb's Journal #102 April 1985.
  4.  */
  5.  
  6. #define   STAND      1
  7. #include <stdio.h>
  8.  
  9. #if STAND
  10. #define MAX_PTRS       500
  11. static char *pp[ MAX_PTRS ];
  12. static int   Lev = 0;               /* Recusion level */
  13. static int   Maxlev = 0;            /* Maximum */
  14. #endif
  15.  
  16. typedef int (* PFI)();              /* Pointer to a function that */
  17.                                     /* returns an int. */
  18. static  PFI    Comp;                /* Pointer to comparsion routine */
  19. static  int    Width;               /* Width of an object in bytes */
  20. /* ------------------------------------------------------------------ */
  21. int argvcmp( slp, s2p )
  22. char **slp,
  23.      **s2p;
  24. /* Comparsion routine for sorting an argv like list of pointers
  25.  * to strings. Just remove one level of indirection and call strcmp
  26.  * to do the comparsion.
  27.  */
  28. {
  29.   return( strcmp( *slp, *s2p ) );
  30. }
  31. qsort( base, nel, width, compare )
  32. char *base;
  33. int   nel,
  34.       width,
  35.       (*compare)();
  36. /* Perform a quick sort on an array starting at base.
  37.  */
  38. {
  39.  
  40.   Width = width;
  41.   Comp = ( compare == (PFI)0 ) ? &argvcmp : compare ;
  42.  
  43.   if ( nel > 1 )
  44.     rqsort( base, base + ( ( nel - 1 ) * width ) );
  45.  
  46. #if STAND
  47.    ptext( nel, base );
  48. #endif
  49.  
  50. }
  51.  
  52. /* ------------------------------------------------------------------ */
  53.  
  54. static  rqsort( low, high )
  55. register char *low,
  56.               *high;
  57. /* Workhorse function called by the access routine, qsort().
  58.  */
  59. {  char *pivot,
  60.         *base;
  61.    static char *a,         /* Used for exchange, will not be needed */
  62.                *b;         /* during recusion, so they can be static.*/
  63.    static int   tmp,       /* That way they will not take up stack   */
  64.                 i;         /* space.                                 */
  65.  
  66.    base = low ;            /* Remember base address of array. */
  67.    pivot = high ;          /* Partition off the pivot.        */
  68.    high -= Width;
  69.  
  70.    do
  71.    {  while ( low < high  &&  (*Comp)(low,  pivot) <= 0 )
  72.         low  += Width;
  73.       while ( low < high  &&  (*Comp)(high, pivot) >= 0 )
  74.         high -= Width;
  75.  
  76.       if ( low < high )      /* Exchange low & high */
  77.       {
  78. /*
  79.          printf( "lev = %d: exchangeing high: <%s> & low <%s>\n",
  80.                       Lev, *((char **)high), *((char **)low));
  81. */
  82.          for ( b = low, a = high, i = Width; --i >= 0; a++, b++ )
  83.          {  tmp = *b;           /* Exchange *low and *high */
  84.             *b  = *a;
  85.             *a  = tmp;
  86.          }
  87.       }
  88.    } while ( low < high );
  89.  
  90.    if ( low < pivot  &&  (*Comp)(low,  pivot) > 0 )
  91.       for ( b = low, a = pivot, i = Width; --i >= 0; a++, b++ )
  92.       {  tmp = *b;           /* Exchange *low and *pivot */
  93.          *b  = *a;
  94.          *a  = tmp;
  95.       }
  96.  
  97.    low += Width;
  98.  
  99.    if ( high - base < pivot - low )
  100.    {
  101.       if ( low  < pivot )
  102.         rqsort( low,  pivot );
  103.       if ( base < high  )
  104.         rqsort( base, high );
  105.    }
  106.    else
  107.    {
  108.       if ( base < high  )
  109.         rqsort( base, high );
  110.       if ( low  < pivot )
  111.         rqsort( low,  pivot );
  112.    }
  113. }
  114.  
  115. /* ------------------------------------------------------------------ */
  116.  
  117. #if STAND
  118. static ptext( argc, argv )
  119. int    argc;
  120. char **argv;
  121. /* Print out argv, one element per line */
  122. {  register int i;
  123.  
  124.    for ( i = 1; --argc >= 0; i++ )
  125.      printf( "%s\n", *argv++ );
  126. }
  127.  
  128. main( argc, argv )
  129. int    argc;
  130. char **argv;
  131. {  char *malloc(),
  132.         *wk;
  133.  
  134.    if ( argc > 1 )
  135.      qsort( ++argv, --argc, sizeof(PFI), 0 );
  136.    else
  137.      {  argc = 0;
  138.         while ( 1 )
  139.         {  if ( ( wk = malloc( 80 ) ) == 0 )
  140.             { printf( "\nUnable to Malloc\n" );
  141.               exit( 0 );
  142.             }
  143.            if ( gets( wk ) == NULL )
  144.               break;
  145.            pp[ argc++ ] = wk ;
  146.            if ( argc > MAX_PTRS )
  147.             { printf( "\nToo many items for QSORT\n" );
  148.               exit( 0 );
  149.             }
  150.         }
  151.         printf("\r\n" );
  152.         qsort( pp, argc, sizeof(PFI), 0 );
  153.      }
  154. }
  155. #endif
  156.